#include <vector>
// #include <string>
using namespace std;


class Solution {
public:
    bool exist(vector<string>& board, string word) {
        int row = board.size();
        int col = board[0].size();
        int wlen = word.size();

        vector<vector<bool>> visited(row, vector<bool>(col, false));

        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (board[i][j] == word[0]) {
                    if (dfs(board, word, i, j, 0, visited))
                        return true;
                }
            }
        }
        return false;
    }

private:
    bool dfs(vector<string>& board,
             const string& word,
             int x, int y,
             int idx,
             vector<vector<bool>>& visited)
    {
        if (idx == word.size()) return true; // 全部匹配完

        int row = board.size();
        int col = board[0].size();

        // 越界、字符不匹配、已访问 -> false
        if (x < 0 || x >= row || y < 0 || y >= col) return false;
        if (board[x][y] != word[idx]) return false;
        if (visited[x][y]) return false;

        // 标记访问
        visited[x][y] = true;

        // 四个方向（上、下、左、右）
        int dx[4] = {1, -1, 0, 0};
        int dy[4] = {0, 0, 1, -1};

        for (int k = 0; k < 4; ++k) {
            if (dfs(board, word, x + dx[k], y + dy[k], idx + 1, visited))
                return true;
        }

        // 回溯：撤销访问标记
        visited[x][y] = false;
        return false;
    }
};